#_*_coding:utf-8_*_
'''
    剑指offer  57_2   和为s的连续正数序列

    输入一个正整数 target，输出所有和为 target的连续正整数序列（至少含有两个数）
    序列内的数字由小到大排序，不同序列按照首个数字从小到大排列


示例 1：
    输入：target = 9
    输出：[[2,3,4],[4,5]]

示例 2：
    输入：target = 15
    输出：[[1,2,3,4,5],[4,5,6],[7,8]]
     

限制：
    1 <= target <= 10^5



'''
from typing import List

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        '''
            滑动窗口解决问题

            滑动窗口的重要性质：窗口的左边界和右边界只能向右移动，而不能向左移动，
            这是为了保证滑动窗口的时间复杂度为O(n),如果左右边界向左移动的话，这叫
            做“回溯”，算法的时间复杂度可能不止 O(n)

            我们关注的是滑动窗口中所有数的和，当滑动窗口的右边界向右移动时，也就是
            j+=1，窗口多了一个数字j，窗口的和也就要加上j，当滑动窗口的左边界向右移
            动时，也就是i+=1，窗口中少了一个数字i，窗口的和也要减去i。
                所以滑动窗口只有：右边界向右移动（扩大窗口）
                                左边界向左移动（缩小窗口）

            注意：1，窗口何时扩大，何时缩小？
                当窗口的和小于target的时候，窗口的和需要增加，所以要扩大窗口
                当窗口的和大于target的时候，窗口的和需要减少，所以需要缩小窗口
                当窗口的和恰好等于target的时候，我们需要记录此时的结果，设此时的
                    窗口为[i, j) 那么我们已经找到一个i开头的序列，也是唯一一个i
                    开头的序列，接下来需要找i+1开头的序列，所以窗口的左边界要向
                    右移动。

            注意2：滑动窗口一定可以找到所有解！！！ 这个可以证明
                时间复杂度为O(n)


            实际上，把题目中的正整数序列换成任意的递增整数序列，此题也可以解。
        '''
        i=1  # 滑动窗口的左边界
        j=1  # 滑动窗口的右边界
        sum=0  # 滑动窗口中数字的和
        res = []
        while i <= target//2:
            if sum < target:
                # 右边界向右移动
                sum += j
                j += 1
            elif sum > target:
                # 左边界向右移动
                sum -= i
                i += 1
            else:
                # 记录结果
                arr = list(range(i,j))
                res.append(arr)

                # 左边界向右移动
                sum -= i
                i += 1
        return res 


target = 9
print(Solution().findContinuousSequence(target))
